package com.tys.algorithm.advanced.code.class17;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

/**
 * 迪瑞克斯拉算法
 * 1 必须指定一个源点
 * 2 生成一个源点到各个带你的最小距离表，一开始只有一条记录，
 * 即原点到自己的最小距离为0，源点到其他所有点的最小距离都为正无穷大
 * 3 从距离表中拿出没拿过记录里的最小记录，通过这个带你发出的边，
 * 更新源点到各个点的最小距离表，不断重复这一步
 * 4 源点到所有点记录如果都被拿过一遍，过程停止，最小距离表得到了
 * 有向无负权重，可以有环
 * 给定a，找到a到所有点的最短距离
 * 没有到f的，就认为a到f位正无穷
 * <p>
 * no negative weight
 */
public class Code01_Dijkstra {

    //方法1：
    public static HashMap<Node, Integer> dijkstra1(Node from) {
        //距离表
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        //自己到自己的距离是0
        distanceMap.put(from, 0);
        // 打过对号的点
        HashSet<Node> selectedNodes = new HashSet<>();
        //距离表中，不是打对号的点，哪个最小
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            //  原始点  ->  minNode(跳转点)   最小距离distance
            int distance = distanceMap.get(minNode);
            //遍历跳转点的边
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to; //边的出度点
                if (!distanceMap.containsKey(toNode)) {
                    //第一次
                    //原始点到跳转点的距离+边的距离=原始点到toNode的距离
                    distanceMap.put(toNode, distance + edge.weight);
                } else { // toNode
                    //已经在了，对比表中的值和当前值，选最小值
                    distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            //进对号表，锁定
            selectedNodes.add(minNode);
            //选剩余最小
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    //距离表中，不是打对号的点，选择最小的
    public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Entry<Node, Integer> entry : distanceMap.entrySet()) {
            Node node = entry.getKey();
            int distance = entry.getValue();
            if (!touchedNodes.contains(node) && distance < minDistance) {
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

    public static class NodeRecord {
        public Node node; //点
        public int distance; //距离

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    //加强堆
    public static class NodeHeap {
        //堆
        private Node[] nodes; // 实际的堆结构
        // 反向索引表：key 某一个node， value 上面堆nodes中的位置
        private HashMap<Node, Integer> heapIndexMap;
        // 最优记录： key 某一个节点， value 从源节点出发到该节点的目前最小距离
        private HashMap<Node, Integer> distanceMap;
        private int size; // 堆上有多少个点

        public NodeHeap(int size) {
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        // 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
        // 判断要不要更新，如果需要的话，就更新
        public void addOrUpdateOrIgnore(Node node, int distance) {
            //在堆上：进来过，更新
            if (inHeap(node)) { //update
                //更新node：老的距离和当前距离比较选最小
                distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                //从node出发向上调堆
                insertHeapify(node, heapIndexMap.get(node));
            }
            //没进来过：新增
            if (!isEntered(node)) { //add
                nodes[size] = node; //加入堆
                heapIndexMap.put(node, size); //加入反向索引表
                distanceMap.put(node, distance); //加入距离表
                insertHeapify(node, size++); //向上调整
            }
            //ignore 啥都不做
        }

        //弹出最小记录
        public NodeRecord pop() {
            //封装记录
            NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
            //交换要弹出的节点：0和最后的位置交换
            swap(0, size - 1);
            //反向索引表中索引修改为-1
            heapIndexMap.put(nodes[size - 1], -1);
            //距离表中删除
            distanceMap.remove(nodes[size - 1]);
            // free C++同学还要把原本堆顶节点析构，对java同学不必
            nodes[size - 1] = null; //堆中设置为null
            heapify(0, --size); //调整堆结构
            return nodeRecord;
        }

        //向上调整
        private void insertHeapify(Node node, int index) {
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        //向下调整
        private void heapify(int index, int size) {
            int left = index * 2 + 1;
            while (left < size) {
                int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
                        ? left + 1
                        : left;
                smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
                if (smallest == index) {
                    break;
                }
                swap(smallest, index);
                index = smallest;
                left = index * 2 + 1;
            }
        }

        //节点是否进入过反向索引表
        private boolean isEntered(Node node) {
            return heapIndexMap.containsKey(node);
        }

        //在不在堆上
        private boolean inHeap(Node node) {
            //在堆上：进来过，并且不等于-1
            return isEntered(node) && heapIndexMap.get(node) != -1;
        }

        //交换：堆和反向索引表都要交换
        private void swap(int index1, int index2) {
            heapIndexMap.put(nodes[index1], index2);
            heapIndexMap.put(nodes[index2], index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }
    }

    // 改进后的dijkstra算法
    // 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
    public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
        //先生成一个堆
        NodeHeap nodeHeap = new NodeHeap(size);
        //add: 新加的入堆
        //update: 更新最小的
        //ignore: 已经锁定的，又发现了新路，忽略
        nodeHeap.addOrUpdateOrIgnore(head, 0);
        HashMap<Node, Integer> result = new HashMap<>();
        while (!nodeHeap.isEmpty()) {
            //弹出堆顶：最小
            NodeRecord record = nodeHeap.pop();
            //点
            Node cur = record.node;
            //距离
            int distance = record.distance;
            //边
            for (Edge edge : cur.edges) {
                //新距离出现，调用修改
                nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
            }
            result.put(cur, distance);
        }
        return result;
    }

}